Encrypting systems can be roughly classified into a common key encrypting system and a public key encrypting system. The common key encrypting system uses the same key (secret key) in encrypting and decoding processes, and maintains the security by defining the secret key as the information unknown to the third parties other a transmitter and a receiver. The public key encrypting system uses keys different between encrypting and decoding processes, and maintains the security by defining a key (secret key) for decoding cipher text as secret information for only a receiver instead of publishing to common users a key (public key) for encryption.
One of the techniques in the field of encryption is decrypting technique. The decrypting technique is to estimate secret information such as a secret key from available information such as cipher text etc., and there are a number of methods. One of the techniques recently receiving widespread attention is a method called power analyzing attacks. The power analyzing attacks was devised by Paul Kocher in 1998 to estimate key information in an encryption processor by collecting and analyzing power consumption data obtained when various input data are provided for an encryption processor loaded into a smart card etc. It is known that a secret key of both common key encryption and public key encryption can be estimated from an encryption processor by using the power analyzing attacks.
There are two types of power analyzing attacks, that is, a simple power analysis (hereinafter referred to as an SPA) and a differential power attacks (hereinafter referred to as a DPA). The SPA is a system of estimating a secret key from the characteristics of a single piece of power consumption data in the encryption processor, and the DPA is a system of estimating a secret key by analyzing a difference in a large number of pieces of power consumption data.
The estimating method using the SPA and the DPA for the common key encrypting systems such as a DES and an AES is described in detail in the following non-patent document 1 (hereinafter referred to as the Kocher 99).
The estimating using the SPA and the DPA for the public key encryption such as the RSA encryption, the oval curve encryption, etc. is described in the documents such as the non-patent document 2 (Messerges 99), the non-patent document 3 (Coron 99), etc.
Calculating Method of RSA Encryption (Prior Art)
In the process of decoding an RSA encryption, an exponential remainder calculating process is performed. The exponential remainder calculation is to calculate plain text v by v=ad (mod n) on a secret key d, cipher text a, and a modulo n. Generally, since the bit length of the secret key d in the RSA encryption is 1024 bits or more, it is necessary to perform 21024 multiplications if the d-th powered multiplication is performed in a simple method, thereby disabling the entire calculation to be completed within a practical time.
There is a binary method or a window method as an algorithm for efficiently performing the process. The binary method is described on page 614, algorithm 14.79 of the following non-patent document 4. The window method is described on page 615, algorithm 14.82 of the document 4. Using these methods, the necessary calculation frequency for the d-th powered multiplication can be reduced from 21024 to a multiple of a constant (1.5 or less) of 1024, thereby realizing an efficiency calculation.
The secret key d is expressed by a u-bit value, and the binary expression is d=(du-1, du-2, . . . , d0)2. However, di indicates a bit value of each “d”. FIG. 1 illustrates the algorithm of the exponential remainder calculation in the binary method, and FIG. 2 illustrates the algorithm of the exponential remainder calculation for calculating v=ad mod n by the window method.
FIG. 3 illustrates the outline of the calculation performed in the binary method illustrated in FIG. 1, and FIG. 4 illustrates the outline of the calculation performed in the window method illustrated in FIG. 2.
The process illustrated in FIG. 1 is described below. The bit value di of d is checked in the order from i=u−1 to i=0. As a result of the check, if di=1, both a squaring and a multiplication are performed. If di=0, only the squaring is performed. By repeating the process from i=u−1 to i=0, the calculation of v=ad (mod n) is performed. That is, the characteristic of the binary method is that the value of the key bit di directly cooperates with the execution pattern of the squaring and the multiplication.
The process illustrated in FIG. 2 is described below. The process of generating w[x]=ax(mod n) is first performed on 0<x<2k. After the table generating process, the d=(du-1, du-2, . . . , d0)2 in the u-bit value is divided into k-bit units to generate Ceiling(u/k) sequences bi (i=0, 1, . . . ). That is, bi=(dik+k−1, . . . , dik)2. The Ceiling(x) indicates the minimum value of the integer equal to or exceeding x. For example, Ceiling(7/3)=Ceiling(2.333 . . . )=3 and Ceiling(10/5)=Ceiling(2)=2. The Ceiling(u/k) indicates the number of divisions when the u-bit bit string is divided into k-bit units. By repeating the table indexing process (v=v′w[bi]) using bi, and the 2k-th powered multiplication (a squaring is performed k times) expressed by v=v2^k(mod n), v=ad(mod n) is calculated. Unlike the binary method, the pattern in which the squaring is repeated k times and the multiplication is performed once is repeated regardless of the value of the key bit di in the window method.
In the following explanation, the sequence bi used in the table index in the window method is referred to as a “window sequence”.
<Power Analyzing Attacks Against the RSA Encrypting Process (Prior Art)>
The power analyzing attacks against the RSA encrypting process described with reference to FIGS. 1 and 2 are described below.
The means and results of attacks depend on the RSA processing method, that is, whether the RSA processing method is the binary method or the window method described below.
Binary Method
Information determined by an attacker from power consumption: Squaring or multiplication is identified.
Key information obtained by an attacker: All bit values (all u bits) of a secret key
Window Method
Information determined by an attacker from power consumption: Whether each window sequence bi is an even number or an odd number.
Key information obtained by an attacker: Ceiling(u/k) bits in u bits of a secret key are decrypted. One bit is decrypted every k-th bit.
As described above, if the bit value of a secret key is 1 in the binary method, then a multiplication and a squaring are performed. If the bit value is 0, then only the squaring is performed. Therefore, in the binary method, if the squaring or the multiplication can be identified depending on the power consumption, all bits of d can be decrypted.
However, in the window method, the execution patterns of the squaring and the multiplication are always constant regardless of the value of the secret key. Therefore, no attacks can be effective in the method of identifying squaring or multiplication as described above. Instead, it is determined whether each window sequence bi is an even number or an odd number using a power consumption waveform. By performing the determination, the least significant bit of bi as the k-bit value can be decrypted. As illustrated in FIG. 4, the window sequence bi is a value delimiting the secret key d in k bit units. Therefore, the bit value of d can be decrypted for each bit every k-th bit.
<Power Analyzing Attacks Against the Binary Method (FIG. 1)>
The method of identifying squaring or multiplication is described below using a power consumption waveform. The identifying method is known as the two following attack methods, that is, the attack method 1 and the attack method 2. Used in these identifying methods is the characteristic that the power consumption waveform of a multiplying process depends on the data value of a multiplication.
Attack Method 1
After inputting a=−1 (mod n) as a value of the cipher text a, the decoding process is performed using the secret key d, and the power consumption is measured. By inputting the cipher text, that is, a=−1 (mod n), the pattern of the data value of the multiplication performed in the decoding process is limited to the following three types.
Multiplication: one type—(1)×(−1)
Squaring: two types—(1)×(1), (−1)×(−1)
FIG. 5 is an example of a power consumption waveform when a=−1 (mod n) is input for d=(10100)2. While a total of seven calculations including multiplication and squaring are performed, only three patterns are applied to the waveforms of power consumption. An attacker observes these waveform patterns, and identifies the execution order of squaring and multiplication.
The attacker has to identify the three types of waveform patterns, and then determines whether each waveform pattern corresponds to the multiplication or the squaring. However, since there are at most six variations of combinations of three types of waveform patterns and the multiplication and the squaring, the values of the key can be limited to 6 types. When the value of d is 1024 bits, 21024 operations are required to obtain a key by a round robin algorithm, but this method can limit the operations to 6 calculations.
When the characteristics of the algorithm in FIG. 1 is further considered, the six calculations can be reduced to one calculation. First, since the waveform to be first used is necessarily (1)×(1) based on the characteristic of the algorithm in FIG. 1, it can be determined which waveform is used as a multiplication waveform for (1)×(1) in the three types of waveform patterns. Since the waveform pattern after performing the multiplication of (1)×(1) is limited to the two types from the characteristic of the algorithm illustrated in FIG. 1, that is, (1)×(1) and (1)×(−1), it is determined that the waveform pattern after the leftmost waveform pattern of (1)×(1) in FIG. 5 is (1)×(−1) because of the difference of the waveform. Thus, the waveform pattern after the leftmost multiplication waveform of (1)×(1) is the waveform of (1)×(−1). Since the waveform pattern of squaring expressed by (−1)×(−1) must be immediately after the multiplication of (1)×(−1) from the characteristic of the algorithm illustrated in FIG. 1, the waveform of (−1)×(−1) can also be determined.
When the value other than −1 is input to a, the data value of the multiplication performed in the loop of the multiplication and squaring of i=u−1, . . . , 1, 0 in FIG. 1 is not limited to the three types above, but the multiplying process can be performed using the data value different each time the multiplication and the squaring are performed. Therefore, all multiplication waveforms are different and appear to an attacker as a list of random waveform patterns. Accordingly, squaring or multiplication cannot be identified. Therefore, only when a=−1 is input, the data value of the multiplication is limited to three patterns, thereby enabling squaring or multiplication to be identified because the patterns of waveforms are limited to three types.
Attack Method 2
In the attack method 1, squaring or multiplication is identified by inputting a=−1(mod n) and observing a single power waveform. On the other hand, in the attack method 2 described below, the power consumption waveform obtained when a=s(mod n) is input and the power consumption waveform obtained when a=−s(mod n) is input are separately measured, and the difference waveforms are observed, thereby identifying squaring or multiplication. In this case, s indicates an optional data value, and can be freely selected by an attacker.
As with the attack method 1, the identifying method of the attack method 2 also has the characteristic that the power consumption waveform in the multiplying process depends on the data value of multiplication.
The difference waveform between the power consumption waveform obtained when a=s(mod n) is input and the power consumption waveform obtained when a=−s(mod n) is input is limited to three patterns depending on whether the calculation being performed is multiplication or squaring. The principle is first described below.
When the power consumption waveform obtained when a=s(mod n) is input is compared with the power consumption waveform obtained when a=−s(mod n) is input with the same timing, the contents of the calculations performed with the respective power consumption waveforms are described below.
Multiplication: The available pattern of the data values of multiplication is one pattern below.
[Pattern 1]
When a=s is input, the multiplication of vs=v×s (mod n) is performed. where v is intermediate data being calculated, and a variable v in FIG. 1.
When a=−s is input, the multiplication of −vs=v×−s (mod n) is performed. where v is intermediate data being calculated, and a variable v in FIG. 1. The value of v is equal to the value of v when a=s is input.
In the case of “pattern 1”, the difference in data value in the multiplying process of C=A×B (mod n) between when a=s is input and when a=−s is input is considered. The values of A are the same, but the values of C and B are different. Therefore, as for the difference waveform between when a=s is input and when s=−s is input in the multiplying process, the waveform difference of the processed portion for the value of A is flat while the processed portions for the values of B and C indicate waveforms of large amplitude because of different data values.
Squaring: The available patterns of the data values of squaring is two patterns below.
[Pattern 2]
When a=s is input, the squaring of v2=v×v (mod n) is performed. where v is intermediate data being calculated, and a variable v in FIG. 1.
When a=−s is input, the squaring of v2=−v×−v (mod n) is performed. where v is intermediate data being calculated, and a variable v in FIG. 1. The value of v is equal to the value of v when a=s is input.
In the case of “pattern 2”, the difference in data value in the multiplying process of C=A×B (mod n) between when a=s is input and when a=−s is input is considered. The values of C are the same, but the values of A and B are different. Therefore, as for the difference waveform between when a=s is input and when s=−s is input in the multiplying process, the waveform difference of the processed portion for the value of C is flat while the processed portions for the values of A and B indicate waveforms of large amplitude because of different data values.
[Pattern 3]
When a=s is input, the multiplication of v2=v×v (mod n) is performed. where v is intermediate data being calculated, and a variable v in FIG. 1.
When a=−s is input, the multiplication of v2=v×v (mod n) is performed. where v is intermediate data being calculated, and a variable v in FIG. 1. The value of v is equal to the value of v when a=s is input.
In the case of “pattern 3”, the difference in data value in the multiplying process of C=A×B (mod n) between when a=s is input and when a=−s is input is considered. All values of A, B, and C are the same. Therefore, as for the difference waveform between when a=s is input and when s=−s is input in the multiplying process, the waveform is completely flat because all values of A, B, and C are the same values.
As described above, the difference waveform obtained between when a=s is input and when a=−s is input can be limited to the waveforms of three patterns depending on the calculation being performed, that is, multiplication of squaring. FIG. 6 is an example of the difference waveform based on the characteristic above.
As illustrated in FIG. 6, a waveform pattern of three types only is obtained by setting the difference waveform obtained between when a=s is input and when a=−s is input. The squaring by the “pattern 3” indicates a completely flat waveform, can be easily identified, and corresponds to the first waveform in FIG. 6. Due to the characteristic of the algorithm in FIG. 1, the squaring of the “pattern 3” is first performed. It is finally necessary to identify the between the multiplication by the “pattern 1” and the squaring by the “pattern 2”, but since there are only two types of the correspondence between the “pattern 1” and the “pattern 2” and the multiplication and the squaring even in the round robin algorithm, the value of the key can be narrowed to two types although the correspondence is not known. Furthermore, if a single or a plurality of waveforms of “pattern 3” continue, from the characteristic of the algorithm in FIG. 1, the “pattern 1” is set. Therefore, the “pattern 1” as a difference waveform can be uniquely identified. In the case in FIG. 6, the waveform as the second waveform from the left corresponds to the “pattern 1”. The waveform of the “pattern 1” in FIG. 6 indicates the characteristic that the left portion is flat and the width of the other portions is large. From the characteristic of the algorithm in FIG. 1, the last “pattern 2” comes immediately after the “pattern 1”. In the case in FIG. 6, the waveform as the second waveform from the left corresponds to the “pattern 1”. The waveform of the “pattern 1” in FIG. 6 indicates the characteristic that the right portion is flat and the width of the other portions is large.
As described above, the attacker identifies the waveform of the “pattern 1”, “pattern 2”, or “pattern 3”, thereby identifying squaring or multiplication and obtaining all values of secret key.
<Power Analyzing Attacks Against Window Method (FIG. 2)>
The method of identifying the window sequence bi as an even number or an odd number is described below using a power consumption waveform. The identifying method is known as the two following attack methods, that is, the attack method 3 and the attack method 4. Used in these identifying methods is the characteristic that the power consumption waveform of a multiplying process depends on the data value of a multiplication.
Attack Method 3
As with the attack method 1, after inputting a=−1(mod n) as a value of the cipher text a, the decoding process is performed using the secret key d, and the power consumption is measured. By inputting the cipher text, that is, a=−1(mod n), the pattern of the data value of the multiplication performed in the decoding process is limited to the following three types as with the attack method 1.
Multiplication: two types—(1)×(−1) or (1)×(1)
Squaring to be performed k times: two types—After once performing (−1)×(−1), (1)×(1) is performed k−1 times or (1)×(1) is performed k times.
In the calculations above, the attacker has to identify two types of multiplication. (It is not necessary to identify two types of squaring.) The identification of the multiplication is necessary because the multiplication of (1)×(−1) indicates bi as an odd number, and the multiplication of (1)×(1) indicates bi as an even number. The cooperation of the even number and the odd number of bi and the type of multiplication is performed because the multiplication v=v×w[bi] using a table w[bi] expressed by w[bi]=abi (mod n) is performed as illustrated in FIG. 2, thereby obtaining the table w[bi] as −1 powered by an odd number, that is, −1, if a=−1 and bi is an odd number, while obtaining the table w[bi] as −1 powered by an even number, that is, 1 if bi is an even number.
As described above, if two types of multiplication can be identified by a power waveform, it can be determined whether bi is an even number or an odd number. Afterwards, two types of multiplication can be identified if an attacker is informed of the timing of the performance of the multiplication, which is quite simple because, from the characteristic of the algorithm illustrated in FIG. 2, a regular process of only performing the multiplication after performing the squaring k times, thereby enabling the attacker to be informed that the multiplication is necessarily performed with the waveform after the squaring is performed k times.
Therefore, the attacker can identify the window sequence bi as an even number or an odd number by identifying the two types of multiplication only on the waveform with the timing of the performance of the multiplication.
FIG. 7 is an example of the power consumption waveform when a=−1(mod n) is input for k=3, d=(101100)2. The calculation pattern in which the squaring is performed three times and the multiplication is performed once is repeated once, and a total of eight calculations are performed. The attacker can determine whether bi is an odd number or an even number by observing the waveform of the multiplication performed every fourth calculation. In this case, since d is 6 bits, a calculation using two windows of b1, b0 is performed. In this case, b1 is higher order 3 bits of d, and b0 is low order 3 bits of d. First, after the squaring by (1)×(1) is performed three times, the multiplication by w[bi] is performed. The multiplication waveform is the fourth waveform from the left, and is quite different from the multiplication waveform of (1)×(1). Therefore, b1 can be identified as an odd number. (If the fourth waveform from the left is the same as the multiplication waveform of (1)×(1), b1 can be identified as an even number.
Then, after the squaring of (−1)×(1) is once performed and the squaring of (1)×(1) is twice performed, the multiplication by w[b0] is performed. The multiplication waveform is the eighth form from the left (or the rightmost waveform), and has the same form as the multiplication waveform of (1)×(1). Therefore, b0 can be identified as an even number.
As described above, the attacker can decrypt that the bit value of d is d=(**1**0)2, and can decrypt two bits in 6 bits of d for every 3 bits.
Attack Method 4
As with the attack method 2, each of the power consumption waveform obtained when a=s(mod n) is input and the power consumption waveform obtained when a=−s(mod n) is input is measured, and the difference waveform is observed with respect to the multiplication, thereby allowing bi to be determined as an even number or an odd number where s is an arbitrary data value and the attacker can freely select the value.
As with the description of the attack method 3, the multiplication of v=v×w[bi] using the table w[bi] expressed in w[bi]=abi (mod n) is performed in the algorithm in FIG. 2. Since the difference of the multiplication data w[bi] between when a=s is input and when a=−s is input depends on whether bi is an even number or an odd number, bi can be identified as an even number or an odd number using the difference of the multiplication waveform.
When bi is an even number, a=s and a=−s generate the same data w[bi]=sbi (mod n). Therefore, when the difference between a=s and a=−s is obtained on the multiplication waveform of v=v×w[bi], a flat waveform is obtained. On the other hand, when bi is an odd number, a=s generates w[bi]=sbi (mod n), but a=−s generates w[bi]=−sbi (mod n). Therefore, when the difference between a=s and a=−s is obtained on the multiplication waveform of v=v×w[bi], a waveform having large amplitude is obtained.
FIG. 8 is an example of the power consumption waveform when a=s and a=−s is input for k=3, d=(101100)2. The calculation pattern in which the squaring is performed three times and the multiplication is performed once is repeated once, and a total of eight calculations are performed. The attacker can determine whether bi is an odd number or an even number by observing the waveform of the multiplication performed every fourth calculation. In this case, since d is 6 bits, a calculation using two windows of b1, b0 is performed. In this case, b1 is higher order 3 bits of d, and b0 is low order 3 bits of d. First, after the squaring by (1)×(1) is performed three times, the multiplication by w[bi] is performed. The multiplication waveform is the fourth waveform from the left, and the difference waveform between a=s and a=−s is not a completely flat waveform. Therefore, b1 can be identified as an odd number. (If the fourth difference waveform from the left is the same as the completely flat waveform, b1 can be identified as an even number.)
Then, after the squaring is performed three times, the multiplication by w[b0] is performed. The multiplication waveform is the eighth form from the left (or the rightmost waveform), the difference waveform is completely flat. Therefore, b0 can be identified as an even number.
As described above, the attacker can decrypt that the bit value of d is d=(**1**0)2, and can decrypt two bits in 6 bits of d for every 3 bits.
By the consideration above, the present invention solves the following problems.
Problem 1: Using the binary method, a safe RSA encrypting process is performed on the attack methods 1 and 2.
Problem 2: Using the window method, a safe RSA encrypting process is performed on the attack methods 3 and 4.
To solve the problems 1 and 2, it is necessary to perform a safe process on the attack methods 1, 2, 3, and 4. Each attack method has the characteristic that the power consumption in the multiplying process depends on the data value of the multiplication. That is, the characteristic with respect to the power consumption causes the problems. The descriptions can be summed up as follows
Attack Method 1
When a=−1 is input, only the following three types of calculations are performed. By identifying these three types by the power waveform, all bit values of d are decrypted.
multiplication: one type of (1)×(−1)
squaring: two types of (1)×(1) and (−1)×(−1).
Attack Method 2
The waveform difference obtained between when a=s is input and when a=−s is input occurs in the following three types of calculations. By identifying these three types by the power waveform, all bit values of d are decrypted.
multiplication: the difference between the waveform of (v)×(s) and the waveform of (v)×(−s) (one type)
squaring: the difference between the waveform of (−v)×(−v) and (v)×(v), or the difference between the waveform of (v)×(v) and (v)×(v) (two types).
Attack Method 3
When a=−1 is input, only the following two types of calculations are performed. By identifying these two types by the power waveform, 1/k bit values of all of d are decrypted.
multiplication: (1)×(−1), (1)×(1)
Attack Method 4
The waveform difference obtained between when a=s is input and when a=−s is input occurs only in the following two types of multiplications. By identifying these two types by the power waveform, 1/k bit values of all of d are decrypted.
multiplication: the difference between the waveform of (v)×(s) and the waveform of (v)×(−s), or the difference between the waveform of (v)×(s) and the waveform of (v)×(s) (two types).
The following non-patent documents 1 through 4 are cited in the explanation above.
Non-patent Document 1: Paul Kocher, Joshua Jaffe, and Benjamin Jun, “Differential Power Analysis,” in proceedings of Advances in Cryptology-CRYPTO '99, Lecture Notes in Computer Science vol. 1666, Springer-Verlag, 1999, pp. 388-397 (hereinafter referred to as Kocher 99)
Non-patent Document 2: Thomas S. Messerges, Ezzy A. Dabbish and Robert H. Sloan “Power Analysis Attacks of Modular Exponentiation in Smartcards”, Cryptographic Hardware and Embedded Systems (CHES' 99), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp. 144-157 (hereinafter referred to as Messerges 99)
Non-patent Document 3: Jean-Sebastein Coron “Resistance against Differential Power Analysis for Elliptic Curve Crytosystems”, Cryptographic Hardware and Embedded Systems (CHES' 99), Lecture Notes in Computer Science vol. 1717, Springer-Verlag, pp. 292-302, 1999 (hereinafter referred to as as Coron 99)
Non-patent Document 4: Alfred J. Menezes et al. “HANDBOOK OF APPLIED CRYPTOGRAPHY” (CRC press), (http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf) In addition, relating to the problems of the present invention, the following patent documents 1 through 3 describe published examples.
Patent Document 1: National Publication of International Patent Application No. 2004-519132
Patent Document 2: Japanese Laid-open Patent Publication No. 2002-261753
Patent Document 3: Japanese Laid-open Patent Publication No. 2004-226674